package programmingpearls.samples;

import java.util.Random;

public class BinarySearch {

    /**
     * @param array
     * @param k
     * @return -1 if array is null or empty, or k is not in array; index if
     *         array[index] == k;
     */
    public static int binarySearch(int[] array, int k) {
        if (array == null || array.length == 0)
            return -1;

        int head = 0;
        int tail = array.length;
        int mid = (head + tail) / 2;
        while (mid >= 0 && mid <= array.length - 1) {
            if (k < array[mid]) {
                tail = mid - 1;
            } else if (k > array[mid]) {
                head = mid + 1;
            } else {
                return mid;
            }
            mid = (head + tail) / 2;
        }
        return -1;

    }

    public static boolean isAscSortedArray(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1])
                return false;
        }
        return true;
    }

    public static boolean isDescSortedArray(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] < array[i + 1])
                return false;
        }
        return true;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] array = new int[100000000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            int k = random.nextInt(200000000);
            System.out.print("Searching : " + k + "\t");
            long start = System.nanoTime();
            int index = BinarySearch.binarySearch(array, k);
            long interval = System.nanoTime() - start;
            if (index == -1)
                System.out.print("Not in array!");
            else {
                System.out.print("Found in array[" + index + "]\t");
            }
            System.out.println("Spend " + interval + "ns");
        }

    }

}
